// 解题思路：
// 这是一道另类的连通块的题目
// 给一个二维数组，例如 m[i][j] == 1 表示 i 城市和 j 城市挨着
// 要找的是城市的连通块，而不是二维数组的连通块
// 找城市的连通块就需要遍历每一个城市，找找与它紧挨着的城市，找到另一个城市之后，再找找与它紧挨着的城市
// 因此就需要用到递归，每次找到一个城市就标记一下，直到整个连通块都找到
// 再找下一个连通块
// 最后返回连通块的数量

import java.util.ArrayList;

public class Cities {
    public boolean[] check;
    public int n;
    public int citys (ArrayList<ArrayList<Integer>> m) {
        n = m.size();
        check = new boolean[n];
        int ret = 0;
        for(int i = 0; i < n; i++){
            if(check[i] == false){
                ret++;
                dfs(m, i);
            }
        }
        return ret;
    }
    public void dfs(ArrayList<ArrayList<Integer>> m, int pos){
        check[pos] = true;
        for(int i = 0; i < n; i++){
            if(m.get(pos).get(i) == 1 && check[i] == false){
                dfs(m, i);
            }
        }
    }
}
